from maze_cell import *
import random

class Maze(object):
    """ This object holds a grid of cells that have walls. It also generates the
    maze by operating on those cells
    """

    def __init__(self, config):
        self.config = config

        #Max X and Max Y are the horizontal and vertical grid size of the maze -
        # it's calculated at run time from the size of the screen set in the
        # Config and the size of each tile. For example, if the screen_size is
        # 800x600 and the tile size is 32, then there are 800 / 32 = 25 tiles
        # across
        self._max_x = int(self.config.screen_size[0] / self.config.tile_size)
        self._max_y = int(self.config.screen_size[1] / self.config.tile_size)

        #Do the Work of generating the Maze from scratch
        self.cells = self.make_depth_first_maze()

    #When the maze is ready to be displayed on screen, it loops through each of
    # its Cells and asks for the CellVisuals object, which contains all the data
    # for how the ground of the maze should look
    def show_cells(self):
        cells = []
        for row in self.cells:
            for cell in row:
                cells.append(cell.show())

        return cells

    #Originally, each cell would make its only walls, which kind of worked. The
    # problem is that in this program, if there's a wall on the EAST of a cell,
    # for example, it's 100% certain that there is a wall on the WEST edge of
    # the neighboring cell. That's not a bug per se, but it means that instead
    # of rendering one wall where there was one wall, the program was rendering
    # 2 walls where there was one wall. Totally inefficient.

    #This approach is a little different. I'll explain in the comments below
    def make_walls(self):

        # First I have to get the list of which walls should exist. These are
        # just lists of wall coordinates, not lists of actual wall objects.
        # It turns out that storing and building the vertical and horizontal
        # walls separately was MUCH simpler than the alternative of a jagged
        # multidimensional array containing boolean values
        vertical_wall_list, horizontal_wall_list = self.get_wall_lists()

        # Now that I have the coordinates, I can generate the actual walls.
        # Rendering the walls is easy, and the coordinates are already set, so
        # we can add all the walls we generate, vertical and horizontal, to the
        # same list
        walls = []
        for hwall in horizontal_wall_list:
            walls.append(self.build_horizontal_wall(hwall))

        for vwall in vertical_wall_list:
          walls.append(self.build_vertical_wall(vwall))

        # The outer walls are always present, so they are a special case. Read
        # the function comments for details
        walls.append(self.build_outer_walls())

        return walls

    # This function returns two lists: a list of vertical wall coordinates, and
    # a list of horizontal wall coordinates
    def get_wall_lists(self):
        vertical_wall_list = []
        horizontal_wall_list = []

        #get each row of cells
        for cell_row in self.cells:
            #get each cell in the row
            for cell in cell_row:
                # In this scheme, we only care about the SOUTH wall and the EAST
                # wall of each cell. The reason is that the SOUTH wall IS the
                # NORTH wall of the cell below it. If you think about it, you'll
                # find that if every cell just takes care of the wall to its
                # SOUTH and the wall to its EAST then the whole maze will
                # generate correctly

                # So in this if statement, I'm checking to make sure the cell
                # isn't in the very last row. (the entire border of the maze is
                # always walled, so there's no point in checking if there's a
                # wall to the SOUTH of a cell in the last row: there ALWAYS is!
                # We'll create 4 big outer walls separately.) If the cell isn't
                # in the last row, then I check to see if it has a SOUTH wall.
                # If it does, then I add the cell's coordinates to the list, to
                # let the part of the program that has to generate the walls
                # that this cell needs a wall to its SOUTH.
                if cell.y < self._max_y-1 and cell.walls[SOUTH]:
                    horizontal_wall_list.append ((cell.x,cell.y))

        # This loop is exactly the same as above, except instead of checking to
        # make sure it's not at the bottom, and then if it has a wall to the
        # SOUTH, this one checks to see if the cell is all the way to the right
        # of the maze, and whether there's a wall to the EAST
        for cell_row in self.cells:
            for cell in cell_row:
                if cell.x < self._max_x-1 and cell.walls[EAST]:
                    vertical_wall_list.append ((cell.x,cell.y))

        # It's possible to return more than one variable at once in python.
        # That's what I did here.
        return vertical_wall_list, horizontal_wall_list

    # This function builds the outer walls of the maze. These walls are always
    # present, no matter what, so instead of building an individual wall for
    # each cell on the outside of the maze, instead I just generate 4 large
    # walls that surround the whole thing, for the sake of efficiency
    def build_outer_walls(self):
        return [
            #North Wall
            Wall(0,
                0,
                self.config.screen_size[0],
                self.config.wall_thickness,
                self.config),
            #West Wall
            Wall(0,
                0,
                self.config.wall_thickness,
                self.config.screen_size[1],
                self.config),
            #East Wall
            Wall(self.config.screen_size[0] - self.config.wall_thickness,
                0,
                self.config.wall_thickness,
                self.config.screen_size[1],
                self.config),
            #South Wall
            Wall(0,
                self.config.screen_size[1] - self.config.wall_thickness,
                self.config.screen_size[0],
                self.config.wall_thickness,
                self.config),
        ]

    # This function takes a grid coordinate, and generates a wall to the EAST of
    # the cell at that coordinate
    def build_horizontal_wall(self,cell):
        # First argument for wall is the x coordinate. It's the grid's X times
        # the tilesize, which tells us how far over the tile is from the left
        # edge of the screen. Also, I move it back to the left by half of the
        # width of the wall I'll explain why I did that below
        #
        # Next is the y coordinate: we take 1 more than the given y, times the
        # tile size. If we just took the given y, the wall would end up at the
        # top of the cell, but remember, we're building the SOUTH wall here, so
        # the wall has to be at the top of the NEXT cell. Then I subtract half
        # the width of the wall, that way the wall is shared evenly between the
        # two cells
        #
        # Next is the width of the wall. Since it's a horizontal wall, it should
        # be the width of the whole tile. But notice I added an extra wall
        # thickness to it. Remember before when I moved the wall to the left by
        # half a wall thickness--that, combined with adding this extra thickness
        # means this wall will overlap its neighboring cells by half a wall
        # thickness on either side. Nothing would break if I didn't do it, but
        # adding that thickness makes the corners nice and square. If you modify
        # these lines so that the wall sits exactly on the tile instead of being
        # slightly too big, you'll see the corners of the maze look sort of
        # jagged.
        #
        # Next is height of the wall. Since this is a horizontal wall, the
        # height is just the wall thickness
        return Wall(cell[0] * self.config.tile_size - \
                        self.config.wall_thickness / 2,
                   (cell[1] + 1) * self.config.tile_size - \
                        self.config.wall_thickness / 2,
                    self.config.tile_size + self.config.wall_thickness,
                    self.config.wall_thickness,
                    self.config)

    # This function takes a grid coordinate, and generates a wall to the EAST of
    # the cell at that coordinate
    def build_vertical_wall(self,cell):
        # See the comment in the function above for a more complete overview.
        # Note here that I didn't make the wall slightly too big here like I did
        # in the last one. It wouldn't break anything to do that--in fact, it
        # would appear to be identical, because the area that the larger wall
        # would cover is already covered by the larger horizontal walls. So I
        # kept this function simpler
        return Wall((cell[0]+1) * self.config.tile_size - self.config.wall_thickness / 2,
                    cell[1] * self.config.tile_size,
                    self.config.wall_thickness,
                    self.config.tile_size,
                    self.config)

    # This function generates a maze from scratch using the DFS, of Depth First
    # Search, generation algorithm. It's a simple algorithm, I'll walk you
    # through it below
    def make_depth_first_maze(self):
        # Below is a technique called a "continuation". Basically that just
        # means that I'm making a list of MazeCell objects, that are using the x
        # and y variables from the for loop. In english, I'm counting from 0 to
        # max_y, and every time I count one more y, I'm making a whole new list.
        # In that list I'm counting from 0 to max_x, and every time I count one
        # more x, I'm making a MazeCell with those X, and Y coordinates.
        # So, for example, the very first MazeCell to be created will be created
        # when y == 0 and x also == 0, so the first MazeCell will have the
        # coordinates (0,0) and sit at the top left corner of the maze.
        rows = [[MazeCell(x,y,self.config) \
                for x in range(0,self._max_x)] \
                for y in range(0,self._max_y)]

        # A "Stack" is a common data structure in computer science. It's a list
        # of things that are "last in first out" or LIFO. Think of it like a
        # real stack of plates. If you put a plate on top of the stack, then you
        # want a plate later, you grab that plate off the top. Normally in
        # programming you each "push" to a stack or "pop" from a stack. i.e.
        # placing that plate is called "pushing" the plate, and taking it back
        # off is called "popping" it. In python it's still called "popping" when
        # you remove an item, but adding an item is called "appending" instead
        # of "pushing"
        cell_stack = []

        # The DFS algorithm requires we keep track of the total number of cells
        total_cells = self._max_x * self._max_y

        # Ee have to select the first cell to start the "search" -- see the
        # function comments for details
        current_cell = self.get_start_cell(rows)

        # Keeping track of the Start Cell isn't necessary for DFS, but I use it
        # later to place the player at the same starting location
        self.start_cell = current_cell

        # DFS also requires that we keep track of how many cells we've visited.
        # Since we have the randomly selected starting cell already, we set the
        # visited_cells value to 1
        visited_cells = 1

        # While there are still cells we haven't visited...
        while visited_cells < total_cells:

            # Get all the neighboring cells of the current cells that still have
            # all their walls. If they have their walls, that means they haven't
            # been visited yet
            nbors = self.get_walled_neighbors(rows, current_cell)

            # If the current cell has neighbors that haven't been visited yet...
            if len(nbors) > 0:
                # Pick one of the neighbors at random. I did that by shuffling
                # all the neighbors, and choosing the first one. You might also
                # just generate a random number between 0 and the length of the
                # nbors list, and then use that as the index. It would do the
                # same thing. This just seemed cleaner because it didn't require
                # an extra index variable
                random.shuffle(nbors)

                # Remove the wall between the current cell and the neighbor. In
                # other words, by visited the cell, we've destroyed the wall
                # that stood in between these two cells
                nbors[0].knock_out_wall(current_cell)

                # Add the current cell to the stack of cells for later use
                cell_stack.append(current_cell)

                # Make the neighbor we just visited into the current cell
                current_cell = nbors[0]

                # Record that we've now visited an additional cell
                visited_cells += 1

            # If the current cell doesn't have any neighbors that haven't been
            # visited yet, that means we're done with this path, and we should
            # go back to the last cell we visited that might have unvisited
            # neighbors
            else:
                current_cell = cell_stack.pop()

        # Now that the DFS algorithm has run, each cell has some walls missing--
        # when you put them all together, you'll have a maze!
        return rows

    # Gets the starting cell for the DFS algorithm by just selecting a random
    # row and a random column
    def get_start_cell(self, rows):
        return rows[random.randrange(self._max_y)] \
                   [random.randrange(self._max_x)]

    # Gets a list of unvisited neighbor cells for the DFS algorithm. In this
    # case, neighbors can only be NORTH, SOUTH, EAST, or WEST of the current
    # cell, so only 4 cells are possible neighbors (instead of 8 if you count
    # the diagonal neighbors)
    def get_walled_neighbors(self, area, current_cell):

        # the neighbors list starts out empty
        nbors = []
        x = current_cell.x
        y = current_cell.y

        # If the current cell isn't all the way to the far right of the grid,
        # then check the cell to the right of it. If it has all its walls, that
        # means it's unvisited, so add it to the nbors collection
        if x + 1 < self._max_x and area[y][x+1].has_all_walls():
            nbors.append(area[y][x+1])

        # If the current cell isn't all the way to the far left...
        if x - 1 > -1 and area[y][x-1].has_all_walls():
            nbors.append(area[y][x-1])

        # If the current cell isn't all the way on the bottom of the grid, then
        # check the cell below it. ...
        if y + 1 < self._max_y and area[y+1][x].has_all_walls():
            nbors.append(area[y+1][x])

        # If the current cell isn't all the way on top...
        if y - 1 > -1 and area[y-1][x].has_all_walls():
            nbors.append(area[y-1][x])

        return nbors

